package com.lun.swordtowardoffer2.c02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
	
	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> result = new ArrayList<>();
		
		if(nums.length >= 3) {
			Arrays.sort(nums);
			int i = 0;
			while(i < nums.length - 2) {//i最多遍历到数组倒数第三个位置即可
				twoSum(nums, i, result);
				
				int temp = nums[i];
				while(i < nums.length - 2 && temp == nums[i]) {//跳过重复元素
					i++;
				}
			}
		}		
		return result;
	}

	private void twoSum(int[] nums, int i, List<List<Integer>> result) {
		int j = i + 1;
		int k = nums.length - 1;
		
		while(j < k) {
			int sum = nums[i] + nums[j] + nums[k];
			if(sum == 0) {
				
				result.add(Arrays.asList(nums[i], nums[j], nums[k]));
				
				int temp = nums[j];
				while(j < k && nums[j] == temp) {//跳过重复元素
					j++;
				}
				
			}else if(sum > 0){
				k--;
			}else {
				j++;
			}
		}				
	}
}
